//
//  CombinationSum2.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/6/10.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  40.组合总和 II  ：中等

import UIKit

/*
 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

 candidates 中的每个数字在每个组合中只能使用一次。

 说明：

 所有数字（包括目标数）都是正整数。
 解集不能包含重复的组合。
 示例 1:

 输入: candidates = [10,1,2,7,6,1,5], target = 8,
 所求解集为:
 [
   [1, 7],
   [1, 2, 5],
   [2, 6],
   [1, 1, 6]
 ]
 示例 2:

 输入: candidates = [2,5,2,1,2], target = 5,
 所求解集为:
 [
   [1,2,2],
   [5]
 ]
 */

class CombinationSum2: NSObject {
    
    var resultArr:Array<[Int]> = []
    
    func combinationSum2(_ candidates: [Int], _ target: Int) -> [[Int]] {
    
        if candidates.count == 0{
            return resultArr
        }
        
        let sourceArr = candidates.sorted()
        
        let arr = [Int]()
        
        self.dfs(0, arr, sourceArr, target)
        
        return resultArr
        
    }
    
    func dfs(_ startIndex: Int, _ tmpArr: [Int] , _ sourceArr: [Int] ,_ target: Int){
        
        //print("\(target)")
        if target == 0 {
            resultArr.append(tmpArr)
            //print("\(tmpArr)")
        }
        
        var arr = tmpArr
        for index in startIndex ..< sourceArr.count {
            if target - sourceArr[index] < 0 {
                break;
            }
            if index > startIndex && sourceArr[index] == sourceArr[index - 1]{
                continue
            }
            arr.append(sourceArr[index])
            //print("---------------内部循环第\(startIndex)次")
            self.dfs(index + 1, arr, sourceArr, target-sourceArr[index])
            arr.removeLast()
        }
        
    }
    
    

    
    
    
    func dfs2(_ startIndex: Int, _ tmpArr: [Int] , _ sourceArr: [Int] ,_ target: Int){

        if self.getSumFromArray(tmpArr) > target{
            return;
        }
        
        if self.getSumFromArray(tmpArr) == target {
            resultArr.append(tmpArr)
            print("\(tmpArr)")
        }
        
        var arr = tmpArr
        for index in startIndex ..< sourceArr.count {
            
            if index > startIndex && sourceArr[index] == sourceArr[index - 1]{
                continue
            }
            
            arr.append(sourceArr[index])
            //print("---------------内部循环第\(startIndex)次")
            self.dfs2(index + 1, arr, sourceArr, target)
            arr.removeLast()
        }
    }
    
    //算出数组所有数字的和
    func getSumFromArray(_ arr:[Int])->Int{
        var sum = 0
        for num in arr{
            sum = sum + num
        }
        return sum
    }

    
    //39. 组合总和
    /*
     给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

     candidates 中的数字可以无限制重复被选取。

     说明：

     所有数字（包括 target）都是正整数。
     解集不能包含重复的组合。
     
     示例 1：
     输入：candidates = [2,3,6,7], target = 7,
     所求解集为：
     [
       [7],
       [2,2,3]
     ]
     
     示例 2：
     输入：candidates = [2,3,5], target = 8,
     所求解集为：
     [
       [2,2,2,2],
       [2,3,3],
       [3,5]
     ]
     */
    func dfs3(_ startIndex: Int, _ tmpArr: [Int] , _ sourceArr: [Int] ,_ target: Int){

        if self.getSumFromArray(tmpArr) > target{
            return;
        }
        
        if self.getSumFromArray(tmpArr) == target {
            resultArr.append(tmpArr)
            //print("\(tmpArr)")
        }
        
        var arr = tmpArr
        for index in startIndex ..< sourceArr.count {
            
            arr.append(sourceArr[index])
            //print("---------------内部循环第\(startIndex)次")
            self.dfs2(index, arr, sourceArr, target)
            arr.removeLast()
        }
    }
    
    
    
    
    
    /*
     216. 组合总和 III
     
     找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

     说明：

     所有数字都是正整数。
     解集不能包含重复的组合。
     示例 1:

     输入: k = 3, n = 7
     输出: [[1,2,4]]
     示例 2:

     输入: k = 3, n = 9
     输出: [[1,2,6], [1,3,5], [2,3,4]]
     */
    func combinationSum3(_ k: Int, _ n: Int) -> [[Int]] {
                 
        guard n != 0 else {
            return []
        }
        
        var sourceArr = [Int]()
        for i in 1 ... 9{
            sourceArr.append(i)
        }
        
        self.dfs4(0, [], sourceArr, n, k)
        
        return resultArr
    }
    
    func dfs4(_ startIndex: Int, _ tmpArr: [Int] , _ sourceArr: [Int] ,_ target: Int, _ numK: Int){
        if target == 0 && tmpArr.count == numK{
            resultArr.append(tmpArr)
            return
        }
        
        var tmpArr = tmpArr
        
        for i in startIndex ..< sourceArr.count {
            tmpArr.append(sourceArr[i])
            self.dfs4(i+1, tmpArr, sourceArr, target - sourceArr[i], numK)
            tmpArr.removeLast()
        }
    }
}
